Local area networks (hereinafter "LANs"), as typified by Ethernet networks in accordance with IEEE Standard 802.3, share a fixed amount of bandwidth between multiple host workstations. When the demands of the hosts reach or exceed the capacity of the LAN, throughput decreases and packet delay increases. In order to improve performance, the LAN can be partitioned into a partially switched network using IEEE 802.1d compliant LAN switches. By utilizing such switches, the host workstations can be distributed among multiple switch-connected LAN segments of varying size, so as to minimize and balance the segments. However, determining how to partition, or segment, a LAN and estimating the performance improvements to be realized by a given partitioning scheme are challenging problems.
Different partitioning approaches have utilized various network characteristics in determining how to partition. For example, in the research paper entitled "Topological Design of Local-Area Networks Using Genetic Algorithms" by R. Elbaum and M. Sidi, Proceedings of IEEE INFOCOM '95, pp. 64-71 (1995), Genetic and Simulated Annealing algorithms are employed for solving network partitioning problems. The Elbaum approach segments the network into clusters using bridges and represents the traffic on the LAN segments and bridges to determine the total network delay based on the traffic in the different parts of the network. The Elbaum approach does not, however, allow for biasing or balancing of delay. Moreover, because it uses bridges to segment the network, it allows multiple bridges to attach to a segment, and only two segments to attach to a bridge.
Another approach, found in "Analyser, A Genetic Algorithm Based Network Divider" by C. Farrell, et al, http://www.cs.curtin.edu.au/.about.netman/analyser.html (1994), uses Simulated Annealing for separating the workstations in an existing network into two segments using a so-called "generic network connecting device." The approach concentrates on maximizing and balancing intra-segment traffic, but does not consider multiple segments or characteristics of the segments, such as capacity, nor does it consider characteristics of the partitioning device, such as switch delay.
Yet another approach, outlined by M. Songerwala in "Efficient Solutions to the Network Division Problem", http://www.cs.curtin.edu.au/.about.netman/analyser.html (1995), and which employs the Genetic algorithm, also fails to consider multiple segments, characteristics of the segment, such as capacity, and characteristics of the partitioning device, such as switch delay.
A more detailed discussion of the prior art, and of the algorithms used therein, can be found in the Master's Thesis of Mark R. Nusekabel, dated July 7, 1997, entitled "Switched Network Partitioning Using Tabu Search," University of South Florida, the teachings of which are herein incorporated by reference.
What is needed, therefore, and what is an objective of the present invention, is to provide a system and method for determining optimal partitioning in a partially-switched LAN, which function takes into consideration both inter-segment and intra- segment traffic and characteristics, including attempting to minimize as well as balance the mean delay for the LAN segments, switch characteristics, including switch delay, and the number of workstations per segment.